package Offer.offer;

/**
 * 是否二叉搜索树的后续遍历结果
 *
 * @author leiwenkang
 * @date 2020/4/6
 */
public class Test24是否二叉搜索树的后续遍历结果 {
    public boolean isPostOrder(int[] array) {
        if (array == null || array.length == 0) {
            return false;
        }

        return isPostOrder(array, 0, array.length - 1);

    }

    private boolean isPostOrder(int[] array, int start, int end) {
        if (start == end) {
            return true;
        }
        int rootValue = array[end];
        //根节点左边比其小，右边比其大
        int i;
        for (i = start; i < end; i++) {
            if (array[i] > rootValue) {
                break;
            }
        }

        for (int j = i; j < end; j++) {
            if (array[j] < rootValue) {
                return false;
            }
        }

        return isPostOrder(array, start, i - 1) && isPostOrder(array, i, end - 1);
    }
}
